package algorithms.heap;

import algorithms.sort.ISort;

/**
 * 使用最大堆排序（升序）
 * 
 * 算法性能：O(nlgn)
 * 
 * Robert. W. Floyd给出了一个堆排序的高效实现。思路是构建一个最大堆而
 * 不是最小堆。这样第一个元素就是最大的。接下来，将最大的元素和数组末尾 的元素交换，
 * 这样最大元素就存储到了排序后的正确位置。原来在末尾的
 * 元素变成了新的堆顶。这会违反堆的性质，我们需要将堆的大小减一，然后执
 * Heapify恢复堆的性质。我们重复这个过程，直到堆中仅剩下1个元素。
 * 
 * 这里的实现恰好和其一致。
 * @See{@link algorithms.heap.Heapify#pop(Integer[])}
 * 
 * （对称的，降序使用最小堆，且复用堆的数组）
 * 
 * @author syx
 *
 */
public class HeapSort implements ISort<Integer> {

	@Override
	public Integer[] sort(Integer[] a) {
		Heapify heapify = new Heapify();
		heapify.buildHeapFromArray(a);
		Integer[] result = new Integer[a.length];
		for (int i = 0; i < result.length - 1; i++) {
			heapify.pop(a);
		}
		return a;
	}

}
